package DoblePointer;//给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。
//
// 注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 12
//输出：21
// 
//
// 示例 2： 
//
// 
//输入：n = 21
//输出：-1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 2³¹ - 1 
// 
// Related Topics 数学 双指针 字符串 线性解法👍 171 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class nextGreaterElement {
    public int nextGreaterElement(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int len = s.length();
        /**
         * 首先从后向前找到第一个不递增的值
         * 找到后，再从该值往后找比他大的最小位置，交换这个两个值，然后交换最初递增的范围
         * */
        int left = len-2;
        //当left停下时要么再起始点，要么就找到了一个不递增的值
        while(left >= 0 && chars[left+1] <= chars[left]){
            //从后向前如果递增 则left平移
            left--;
        }
        if(left<0){
            return -1;
        }

        int idx = len - 1;
        while (idx >= 0 && chars[idx] <= chars[left]) {
            idx--;
        }
        swap(chars,left,idx);
        reverse(chars,left+1,len-1);
        try {
            return Integer.parseInt(new String(chars));
        } catch (Exception e) {
            return -1;
        }
    }

    //交换值
    private void swap(char[] ch, int i, int j){
        char temp = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
    }
    //逆转数组
    private void reverse(char[] ch, int i, int j){
        while(i<j){
            swap(ch,i,j);
            i++;
            j--;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
